﻿namespace Leetcode.N0436;
public class Solution
{
    public int[] FindRightInterval(int[][] intervals)
    {
        const int Start = 0, End = 1, Index = 2;
        var n = intervals.Length;

        // 1. 把$intervals[i][start, end]$转换成$intervals[i][start, end,index]$，$index=i$是$intervals$的索引
        for (int i = 0; i < n; i++)
        {
            intervals[i] = new[] { intervals[i][Start], intervals[i][End], i };
        }

        // 2. 按$intervals[i][start]$排序，排序后得到新的$intervals$
        intervals = intervals.OrderBy(i => i[Start]).ToArray();

        var ans = new int[n];
        var queue = new PriorityQueue<int[], int>();

        for (int i = 0; i < n; i++)
        {
            // 3. 遍历新的$intervals[i]$，以$intervals[i][end]$为优先级，加入队列$queue$
            queue.Enqueue(intervals[i], intervals[i][End]);

            // 把队列$queue$中$[end]<=intervals[i][start]$的项目出队，并保存结果
            while (queue.Count > 0 && queue.Peek()[End] <= intervals[i][Start])
            {
                ans[queue.Dequeue()[Index]] = intervals[i][Index];
            }
        }

        // 4. 队列$queue$中剩余的项目结果都为$-1$
        while (queue.Count > 0)
        {
            ans[queue.Dequeue()[Index]] = -1;
        }

        return ans;
    }
}